Search for: All records

Mutualisms are mediated by adaptive traits of interacting organisms and play a central role in the ecology and evolution of species. Thousands of plant species possess tiny structures called “domatia” that house mites which protect plants from pests, yet these traits remain woefully understudied. Here, we release a worldwide database of species with mite domatia and provide an evaluation of the phylogenetic and geographic distribution of this mutualistic trait. With >2,500 additions based on digital herbarium scans and published reports, we increased the number of known species with domatia by 27% and, importantly, documented their absence in >4,000 species. We show that mite domatia likely evolved hundreds of times among flowering plants, occurring in an estimated ~10% of woody species representing over a quarter of all angiosperm families. Contrary to classic hypotheses about the evolutionary drivers of mutualism, we find that mite domatia evolved more frequently in temperate regions and in deciduous lineages; this pattern is concordant with a large-scale geographic transition from predominantly ant-based plant defense mutualisms in the tropics to mite-based defense mutualisms in temperate climates. Our data also reveal a pattern of evolutionary convergence in domatia morphology, with tuft-form domatia more likely to evolve in dry temperate habitats and pit domatia more likely to evolve in wet tropical environments. We have shown climate-associated drivers of mite domatia evolution, demonstrating their utility and power as an evolutionarily replicated system for the study of plant defense mutualisms. 

We report the design conception, chemical synthesis, and microbiological evaluation of the bridged macrobicyclic antibiotic cresomycin (CRM), which overcomes evolutionarily diverse forms of antimicrobial resistance that render modern antibiotics ineffective. CRM exhibits in vitro and in vivo efficacy against both Gram-positive and Gram-negative bacteria, including multidrug-resistant strains ofStaphylococcus aureus,Escherichia coli, andPseudomonas aeruginosa. We show that CRM is highly preorganized for ribosomal binding by determining its density functional theory–calculated, solution-state, solid-state, and (wild-type) ribosome-bound structures, which all align identically within the macrobicyclic subunits. Lastly, we report two additional x-ray crystal structures of CRM in complex with bacterial ribosomes separately modified by the ribosomal RNA methylases, chloramphenicol-florfenicol resistance (Cfr) and erythromycin-resistance ribosomal RNA methylase (Erm), revealing concessive adjustments by the target and antibiotic that permit CRM to maintain binding where other antibiotics fail. 

This paper proposes a new type system for concurrent programs, allowing threads to exchange complex object graphs without risking destructive data races. While this goal is shared by a rich history of past work, existing solutions either rely on strictly enforced heap invariants that prohibit natural programming patterns or demand pervasive annotations even for simple programming tasks. As a result, past systems cannot express intuitively simple code without unnatural rewrites or substantial annotation burdens. Our work avoids these pitfalls through a novel type system that provides sound reasoning about separation in the heap while remaining flexible enough to support a wide range of desirable heap manipulations. This new sweet spot is attained by enforcing a heap domination invariant similarly to prior work, but tempering it by allowing complex exceptions that add little annotation burden. Our results include: (1) code examples showing that common data structure manipulations which are difficult or impossible to express in prior work are natural and direct in our system, (2) a formal proof of correctness demonstrating that well-typed programs cannot encounter destructive data races at run time, and (3) an efficient type checker implemented in Gallina and OCaml. 

Processors are typically designed in Register Transfer Level (RTL) languages, which give designers low-level control over circuit structure and timing. To achieve good performance, processors are pipelined, with multiple instructions executing concurrently in different parts of the circuit. Thus even though processors implement a fundamentally sequential specification (the instruction set architecture), the implementation is highly concurrent. The interactions of multiple instructions---potentially speculative---can cause incorrect behavior. We present PDL, a novel hardware description language targeted at the construction of pipelined processors. PDL provides one instruction at a time semantics: the first language to enforce that the generated pipelined circuit has the same behavior as a sequential specification. This enforcement facilitates design-space exploration. Adding or removing pipeline stages, moving operations across stages, or otherwise changing pipeline structure normally requires careful analysis of bypass paths and stall logic; with PDL, this analysis is handled by the PDL compiler. At the same time, PDL still offers designers fine-grained control over performance-critical microarchitectural choices such as timing of operations, data forwarding, and speculation. We demonstrate PDL's expressive power and ease of design exploration by implementing several RISC-V cores with differing microarchitectures. Our results show that PDL does not impose significant performance or area overhead compared to a standard HDL. 

In distributed systems, a group of learners achieve consensus when, by observing the output of some acceptors, they all arrive at the same value. Consensus is crucial for ordering transactions in failure-tolerant systems. Traditional consensus algorithms are homogeneous in three ways: (1) all learners are treated equally, (2) all acceptors are treated equally, and (3) all failures are treated equally.These assumptions, however, are unsuitable for cross-domain applications, including blockchains, where not all acceptors are equally trustworthy, and not all learners have the same assumptions and priorities. We present the first algorithm to be heterogeneous in all three respects. Learners set their own mixed failure tolerances over differently trusted sets of acceptors. We express these assumptions in a novel Learner Graph, and demonstrate sufficient conditions for consensus. We present Heterogeneous Paxos, an extension of Byzantine Paxos. Heterogeneous Paxos achieves consensus for any viable Learner Graph in best-case three message sends, which is optimal. We present a proof-of-concept implementation and demonstrate how tailoring for heterogeneous scenarios can save resources and reduce latency. 

Modern distributed systems involve interactions between principals with limited trust, so cryptographic mechanisms are needed to protect confidentiality and integrity. At the same time, most developers lack the training to securely employ cryptography. We present Viaduct, a compiler that transforms high-level programs into secure, efficient distributed realizations. Viaduct's source language allows developers to declaratively specify security policies by annotating their programs with information flow labels. The compiler uses these labels to synthesize distributed programs that use cryptography efficiently while still defending the source-level security policy. The approach is general, and can be easily extended with new security mechanisms. Our implementation of the compiler comes with an extensible runtime system that includes plug-in support for multiparty computation, commitments, and zero-knowledge proofs. We have evaluated the system on a set of benchmarks, and the results indicate that our approach is feasible and can use cryptography in efficient, nontrivial ways. 

Monarch butterfly (Danaus plexippus L.) declines in eastern North America have prompted milkweed host plant restoration efforts in non-agricultural grasslands. However, grasslands harbor predator communities that exert high predation pressure on monarch eggs and larvae. While diurnal monarch predators are relatively well known, no studies have investigated the contribution of nocturnal monarch predators. We used video cameras to monitor sentinel monarch eggs and fourth instars on milkweed in southern Michigan to identify predators and determine if nocturnally-active species impose significant predation pressure. We observed ten arthropod taxa consuming monarch eggs and larvae, with 74% of egg predation events occurring nocturnally. Taxa observed attacking monarch eggs included European earwigs (Forficula auricularia L.), tree crickets (Oecanthus sp.), lacewing larvae (Neuroptera), plant bugs (Miridae), small milkweed bugs (Lygaeus kalmii Stal), ants (Formicidae), spiders (Araneae: Salticidae and other spp.), harvestmen (Opiliones), and velvet mites (Trombidiformes: Trombidiidae). Larvae were attacked by ground beetles (Calleida sp.), jumping spiders (Araneae: Salticidae), and spined soldier bugs (Podisus maculiventris Say). Our findings provide important information about monarch predator-prey interactions that could be used to develop strategies to conserve monarchs through reducing predation on early life stages. 

Securing blockchain smart contracts is difficult, especially when they interact with one another. Existing tools for reasoning about smart contract security are limited in one of two ways: they either cannot analyze cooperative interaction between contracts, or they require all interacting code to be written in a specific language. We propose an approach based on information flow control~(IFC), which supports fine-grained, compositional security policies and rules out dangerous vulnerabilities. However, existing IFC systems provide few guarantees on interaction with legacy contracts and unknown code. We extend existing IFC constructs to support these important functionalities while retaining compositional security guarantees, including reentrancy control. We mix static and dynamic mechanisms to achieve these goals in a flexible manner while minimizing run-time costs.